package leetcode;

import util.TreeNode;

import java.util.HashMap;

/**
 * @Project : AlgorithmLearning
 * @Package : Leetcode
 * @File : Q0337.java
 * @Author : WangRuoyu
 * @Date 2023/11/26 22:31
 */

public class Q0337 {
    HashMap<TreeNode, Integer> map = new HashMap<>();

    private int dfs(TreeNode root) {
        if (root == null) return 0;
        if (root.left == null && root.right == null) return root.val;
        if (map.containsKey(root)) return map.get(root);
        int res = dfs(root.left) + dfs(root.right);
        int tmp = root.val;
        if (root.left != null) tmp += dfs(root.left.left) + dfs(root.left.right);
        if (root.right != null) tmp += dfs(root.right.left) + dfs(root.right.right);
        res = Math.max(res, tmp);
        map.put(root, res);
        return res;
    }

    public int rob(TreeNode root) {
        return dfs(root);
    }

    public static void main(String[] args) {
        Q0337 sl = new Q0337();
    }
}